package code;

import java.util.ArrayList;
import java.util.List;


public class PathSumII {
	static public class TreeNode {
	     int val;
	     TreeNode left;
	     TreeNode right;
	     TreeNode(int x) { val = x; }
	}
	
	private List<List<Integer>> result=new ArrayList<List<Integer>>();
	private int n;
	
	public void dfs(int sum,int cnt,int step,int[] rec,TreeNode p){
		cnt+=p.val;
		rec[step]=p.val;
		if(p.left==null && p.right==null){
			if(cnt==sum){
				List<Integer> list=new ArrayList<Integer>();
				for(int i=0;i<=step;i++){
					list.add(rec[i]);
				}
				result.add(list);
			}
		}
		if(p.left!=null){
			 dfs(sum,cnt,step+1,rec,p.left);
		}
		if(p.right!=null){
			dfs(sum,cnt,step+1,rec,p.right);
		}
	}
	public boolean dfsII(int sum,int cnt,TreeNode p){
		cnt+=p.val;
		if(p.left==null && p.right==null){
			if(cnt==sum)
				return true;
		}
		if(p.left!=null){
			 if(dfsII(sum,cnt,p.left))
				 return true;
		}
		if(p.right!=null){
			if(dfsII(sum,cnt,p.right))
				return true;
		}
		return false;
	}
	public void sumOfNode(TreeNode p){
		n++;
		if(p.left==null && p.right==null)	return ;
		if(p.left!=null)
			sumOfNode(p.left);
		if(p.right!=null)
			sumOfNode(p.right);
	}
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null)	
        	return result;	
    	sumOfNode(root);
    	int[] rec=new int[n];
    	dfs(sum,0,0,rec,root);
    	return result;
    }
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)	
        	return false;
        if(dfsII(sum,0,root))
        	return true;
        return false;
    }
    public static void main(String[] args){
    	PathSumII ps=new PathSumII();
    	TreeNode root=new TreeNode(-2);
    	TreeNode a=new TreeNode(-3);
//    	root.right=a;
    	ps.pathSum(root, -2);
    }
}
